<!DOCTYPE html>



  


<html class="theme-next gemini use-motion" lang="zh-CN">
<head>
  <meta charset="UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=edge" />
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1"/>
<meta name="theme-color" content="#222">









<meta http-equiv="Cache-Control" content="no-transform" />
<meta http-equiv="Cache-Control" content="no-siteapp" />















  
  
  <link href="/lib/fancybox/source/jquery.fancybox.css?v=2.1.5" rel="stylesheet" type="text/css" />




  
  
  
  

  
    
    
  

  
    
      
    

    
  

  
    
      
    

    
  

  
    
      
    

    
  

  
    
      
    

    
  

  
    
    
    <link href="//fonts.googleapis.com/css?family=Microsoft YaHei:300,300italic,400,400italic,700,700italic|Microsoft YaHei:300,300italic,400,400italic,700,700italic|Microsoft YaHei:300,300italic,400,400italic,700,700italic|Microsoft YaHei:300,300italic,400,400italic,700,700italic|Inziu Iosevka Slab SC:300,300italic,400,400italic,700,700italic&subset=latin,latin-ext" rel="stylesheet" type="text/css">
  






<link href="/lib/font-awesome/css/font-awesome.min.css?v=4.6.2" rel="stylesheet" type="text/css" />

<link href="/css/main.css?v=5.1.2" rel="stylesheet" type="text/css" />


  <meta name="keywords" content="Hexo, NexT" />








  <link rel="shortcut icon" type="image/x-icon" href="/favicon.ico?v=5.1.2" />






<meta name="description" content="普通 K-meansThe k-means algorithm works like this. First, the k centroids are randomly assignedto a point. Next, each point in the dataset is assigned to a cluster. The assignment is done by finding the">
<meta property="og:type" content="article">
<meta property="og:title" content="K-Means Clustering">
<meta property="og:url" content="http://idmk.oschina.io/2017/08/28/K-means-Clustering/index.html">
<meta property="og:site_name" content="苦舟">
<meta property="og:description" content="普通 K-meansThe k-means algorithm works like this. First, the k centroids are randomly assignedto a point. Next, each point in the dataset is assigned to a cluster. The assignment is done by finding the">
<meta property="og:locale" content="zh-CN">
<meta property="og:image" content="http://idmk.oschina.io/2017/08/28/K-means-Clustering/markdown-img-paste-20170828222759352.png">
<meta property="og:image" content="http://idmk.oschina.io/2017/08/28/K-means-Clustering/markdown-img-paste-20170829103434421.png">
<meta property="og:updated_time" content="2017-11-22T15:33:53.982Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="K-Means Clustering">
<meta name="twitter:description" content="普通 K-meansThe k-means algorithm works like this. First, the k centroids are randomly assignedto a point. Next, each point in the dataset is assigned to a cluster. The assignment is done by finding the">
<meta name="twitter:image" content="http://idmk.oschina.io/2017/08/28/K-means-Clustering/markdown-img-paste-20170828222759352.png">



<script type="text/javascript" id="hexo.configurations">
  var NexT = window.NexT || {};
  var CONFIG = {
    root: '/',
    scheme: 'Gemini',
    sidebar: {"position":"left","display":"hide","offset":12,"offset_float":12,"b2t":false,"scrollpercent":false,"onmobile":false},
    fancybox: true,
    tabs: true,
    motion: true,
    duoshuo: {
      userId: '0',
      author: '博主'
    },
    algolia: {
      applicationID: '',
      apiKey: '',
      indexName: '',
      hits: {"per_page":10},
      labels: {"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}
    }
  };
</script>



  <link rel="canonical" href="http://idmk.oschina.io/2017/08/28/K-means-Clustering/"/>





  <title>K-Means Clustering | 苦舟</title>
  














</head>

<body itemscope itemtype="http://schema.org/WebPage" lang="zh-CN">

  
  
    
  

  <div class="container sidebar-position-left page-post-detail ">
    <div class="headband"></div>

    <header id="header" class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-wrapper">
  <div class="site-meta ">
    

    <div class="custom-logo-site-title">
      <a href="/"  class="brand" rel="start">
        <span class="logo-line-before"><i></i></span>
        <span class="site-title">苦舟</span>
        <span class="logo-line-after"><i></i></span>
      </a>
    </div>
      
        <p class="site-subtitle">学海无涯，吾将上下求索。</p>
      
  </div>

  <div class="site-nav-toggle">
    <button>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
    </button>
  </div>
</div>

<nav class="site-nav">
  

  
    <ul id="menu" class="menu">
      
        
        <li class="menu-item menu-item-home">
          <a href="/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-home"></i> <br />
            
            首页
          </a>
        </li>
      
        
        <li class="menu-item menu-item-categories">
          <a href="/categories/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-th"></i> <br />
            
            分类
          </a>
        </li>
      
        
        <li class="menu-item menu-item-about">
          <a href="/about/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-user"></i> <br />
            
            关于
          </a>
        </li>
      
        
        <li class="menu-item menu-item-archives">
          <a href="/archives/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-archive"></i> <br />
            
            归档
          </a>
        </li>
      
        
        <li class="menu-item menu-item-tags">
          <a href="/tags/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-tags"></i> <br />
            
            标签
          </a>
        </li>
      
        
        <li class="menu-item menu-item-commonweal">
          <a href="/404.html" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-heartbeat"></i> <br />
            
            公益404
          </a>
        </li>
      

      
        <li class="menu-item menu-item-search">
          
            <a href="javascript:;" class="popup-trigger">
          
            
              <i class="menu-item-icon fa fa-search fa-fw"></i> <br />
            
            搜索
          </a>
        </li>
      
    </ul>
  

  
    <div class="site-search">
      
  <div class="popup search-popup local-search-popup">
  <div class="local-search-header clearfix">
    <span class="search-icon">
      <i class="fa fa-search"></i>
    </span>
    <span class="popup-btn-close">
      <i class="fa fa-times-circle"></i>
    </span>
    <div class="local-search-input-wrapper">
      <input autocomplete="off"
             placeholder="搜索..." spellcheck="false"
             type="text" id="local-search-input">
    </div>
  </div>
  <div id="local-search-result"></div>
</div>



    </div>
  
</nav>



 </div>
    </header>

    <main id="main" class="main">
      <div class="main-inner">
        <div class="content-wrap">
          <div id="content" class="content">
            

  <div id="posts" class="posts-expand">
    

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://idmk.oschina.io/2017/08/28/K-means-Clustering/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="东木金">
      <meta itemprop="description" content="">
      <meta itemprop="image" content="/uploads/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="苦舟">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">K-Means Clustering</h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-08-28T17:21:30+08:00">
                2017-08-28
              </time>
            

            

            
          </span>

          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        <h2 id="普通-K-means"><a href="#普通-K-means" class="headerlink" title="普通 K-means"></a>普通 K-means</h2><p>The k-means algorithm works like this. First, the k centroids are randomly assignedto a point. Next, each point in the dataset is assigned to a cluster. The assignment is done by finding the closest centroid and assigning the point to that cluster. After this step, the centroids are all updated by taking the mean value of all the points in that cluster.</p>
<a id="more"></a>
<ul>
<li>Create k points for starting centroids (often randomly)</li>
<li>While any point has changed cluster assignment<ul>
<li>for every point in our dataset:<ul>
<li>for every centroid<ul>
<li>calculate the distance between the centroid and point assign the point to the cluster with the lowest distance</li>
</ul>
</li>
</ul>
</li>
<li>for every cluster calculate the mean of the points in that cluster assign the centroid to the mean</li>
</ul>
</li>
</ul>
<h3 id="算法实现"><a href="#算法实现" class="headerlink" title="算法实现"></a>算法实现</h3><figure class="highlight python"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div><div class="line">22</div><div class="line">23</div><div class="line">24</div><div class="line">25</div><div class="line">26</div><div class="line">27</div><div class="line">28</div><div class="line">29</div><div class="line">30</div><div class="line">31</div><div class="line">32</div><div class="line">33</div><div class="line">34</div><div class="line">35</div><div class="line">36</div><div class="line">37</div><div class="line">38</div><div class="line">39</div><div class="line">40</div><div class="line">41</div><div class="line">42</div><div class="line">43</div><div class="line">44</div><div class="line">45</div><div class="line">46</div><div class="line">47</div><div class="line">48</div><div class="line">49</div><div class="line">50</div><div class="line">51</div><div class="line">52</div><div class="line">53</div><div class="line">54</div><div class="line">55</div><div class="line">56</div><div class="line">57</div><div class="line">58</div><div class="line">59</div><div class="line">60</div><div class="line">61</div><div class="line">62</div><div class="line">63</div><div class="line">64</div><div class="line">65</div><div class="line">66</div><div class="line">67</div><div class="line">68</div></pre></td><td class="code"><pre><div class="line"><span class="keyword">import</span> numpy <span class="keyword">as</span> np</div><div class="line"><span class="keyword">import</span> matplotlib.pyplot <span class="keyword">as</span> plt</div><div class="line"></div><div class="line"></div><div class="line"><span class="function"><span class="keyword">def</span> <span class="title">load_dataset</span><span class="params">(filepath)</span>:</span></div><div class="line">    X = []</div><div class="line">    <span class="keyword">with</span> open(filepath, <span class="string">'r'</span>, encoding=<span class="string">"utf-8"</span>) <span class="keyword">as</span> rf:</div><div class="line">        <span class="keyword">for</span> line <span class="keyword">in</span> rf.readlines():</div><div class="line">            row = line.strip().split(<span class="string">'\t'</span>)</div><div class="line">            fltrow = list(map(float, row))</div><div class="line">            X.append(fltrow)</div><div class="line">    <span class="keyword">return</span> X</div><div class="line"></div><div class="line"></div><div class="line"><span class="function"><span class="keyword">def</span> <span class="title">dist_eclud</span><span class="params">(vec1, vec2)</span>:</span></div><div class="line">    <span class="string">"""calculating the Euclidean distance between twovectors"""</span></div><div class="line">    <span class="keyword">return</span> np.sqrt(np.sum(np.power((vec1 - vec2), <span class="number">2</span>)))</div><div class="line"></div><div class="line"></div><div class="line"><span class="function"><span class="keyword">def</span> <span class="title">rand_cent</span><span class="params">(X, k)</span>:</span></div><div class="line">    n = X.shape[<span class="number">1</span>]</div><div class="line">    centroids = np.mat(np.zeros((k, n)))</div><div class="line">    <span class="keyword">for</span> j <span class="keyword">in</span> range(n):</div><div class="line">        range_min = np.min(X[:, j])</div><div class="line">        range_width = np.max(X[:, j] - range_min)</div><div class="line">        centroids[:, j] = range_min + range_width * np.random.rand(k, <span class="number">1</span>)</div><div class="line">    <span class="keyword">return</span> centroids</div><div class="line"></div><div class="line"></div><div class="line"><span class="function"><span class="keyword">def</span> <span class="title">kmeans</span><span class="params">(X, k, dist_meas=dist_eclud, create_cent=rand_cent)</span>:</span></div><div class="line">    m = X.shape[<span class="number">0</span>]</div><div class="line">    cluster_assment = np.mat(np.zeros((m, <span class="number">2</span>)))</div><div class="line">    centroids = create_cent(X, k)</div><div class="line">    cluster_changed = <span class="keyword">True</span></div><div class="line">    <span class="keyword">while</span> cluster_changed:</div><div class="line">        cluster_changed = <span class="keyword">False</span></div><div class="line">        <span class="keyword">for</span> i <span class="keyword">in</span> range(m):</div><div class="line">            min_dist = np.inf</div><div class="line">            min_idx = <span class="number">-1</span></div><div class="line">            <span class="keyword">for</span> j <span class="keyword">in</span> range(k):</div><div class="line">                dist_ji = dist_meas(centroids[j, :], X[i, :])</div><div class="line">                <span class="keyword">if</span> dist_ji &lt; min_dist:</div><div class="line">                    min_dist = dist_ji</div><div class="line">                    min_idx = j</div><div class="line">            <span class="keyword">if</span> cluster_assment[i, <span class="number">0</span>] != min_idx:</div><div class="line">                cluster_changed = <span class="keyword">True</span></div><div class="line">            cluster_assment[i, :] = min_idx, min_dist ** <span class="number">2</span></div><div class="line">        <span class="comment"># print(centroids)</span></div><div class="line">        <span class="keyword">for</span> cent <span class="keyword">in</span> range(k):</div><div class="line">            pts_in_clust = X[np.nonzero(cluster_assment[:, <span class="number">0</span>].A == cent)[<span class="number">0</span>]]</div><div class="line">            centroids[cent, :] = np.mean(pts_in_clust, axis=<span class="number">0</span>)</div><div class="line">    <span class="keyword">return</span> centroids, cluster_assment</div><div class="line"></div><div class="line"></div><div class="line"><span class="function"><span class="keyword">def</span> <span class="title">test</span><span class="params">()</span>:</span></div><div class="line">    filepath = <span class="string">"./Ch10/testSet.txt"</span></div><div class="line">    X = load_dataset(filepath)</div><div class="line">    x_mat = np.mat(X)</div><div class="line">    centroids, clustassing = kmeans(x_mat, <span class="number">4</span>)</div><div class="line">    <span class="comment"># print(centroids)</span></div><div class="line">    plt.scatter(x_mat[:, <span class="number">0</span>].flatten().getA()[<span class="number">0</span>], x_mat[:, <span class="number">1</span>].flatten().getA()[<span class="number">0</span>], color=<span class="string">'blue'</span>)</div><div class="line">    plt.scatter(centroids[:, <span class="number">0</span>].flatten().getA()[<span class="number">0</span>], centroids[:, <span class="number">1</span>].flatten().getA()[<span class="number">0</span>], color=<span class="string">'r'</span>)</div><div class="line">    plt.show()</div><div class="line">    <span class="comment"># 对聚类到不同的蔟的点标记为不同的类</span></div><div class="line">    <span class="comment"># todo</span></div><div class="line"></div><div class="line"><span class="keyword">if</span> __name__ == <span class="string">"__main__"</span>:</div><div class="line">    test()</div></pre></td></tr></table></figure>
<img src="/2017/08/28/K-means-Clustering/markdown-img-paste-20170828222759352.png" alt="K-means 聚类效果" title="K-means 聚类效果">
<p>注：由于使用了随机生成操作，故每次的结果多少会有些不同。</p>
<h2 id="Improving-cluster-performance-with-postprocessing"><a href="#Improving-cluster-performance-with-postprocessing" class="headerlink" title="Improving cluster performance with postprocessing"></a>Improving cluster performance with postprocessing</h2><p>How does the user know that k is the right number?<br>How do you know that the clusters are good clusters?</p>
<p>One metric for the quality of your cluster assignments you can use is the SSE, or sum of squared error. This is the sum of the values in column 1 of clusterAssment in listing 10.2. A lower SSE means that points are closer to their centroids, and you ’ ve done a better job of clustering.</p>
<p>This algorithm, known as bisecting k-means, starts out with one cluster and then splits the cluster in two. It then chooses a cluster to split. The cluster to split is decided by minimizing the SSE. This splitting based on the SSE is repeated until the user-defined number of clusters is attained.</p>
<p>Pseudocode for bisecting k-means will look like this:</p>
<pre><code>Start with all the points in one cluster
While the number of clusters is less than k
    for every cluster
        measure total error
        perform k-means clustering with k=2 on the given cluster
        measure total error after k-means has split the cluster in two
    choose the cluster split that gives the lowest error (or largest SSE) and commit this split
</code></pre><h3 id="算法实现-1"><a href="#算法实现-1" class="headerlink" title="算法实现"></a>算法实现</h3><figure class="highlight python"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div><div class="line">22</div><div class="line">23</div><div class="line">24</div><div class="line">25</div><div class="line">26</div><div class="line">27</div><div class="line">28</div><div class="line">29</div><div class="line">30</div><div class="line">31</div><div class="line">32</div><div class="line">33</div><div class="line">34</div><div class="line">35</div><div class="line">36</div><div class="line">37</div><div class="line">38</div><div class="line">39</div><div class="line">40</div><div class="line">41</div><div class="line">42</div><div class="line">43</div><div class="line">44</div><div class="line">45</div><div class="line">46</div><div class="line">47</div><div class="line">48</div><div class="line">49</div><div class="line">50</div><div class="line">51</div><div class="line">52</div><div class="line">53</div><div class="line">54</div><div class="line">55</div><div class="line">56</div><div class="line">57</div><div class="line">58</div><div class="line">59</div><div class="line">60</div><div class="line">61</div><div class="line">62</div><div class="line">63</div><div class="line">64</div><div class="line">65</div><div class="line">66</div><div class="line">67</div><div class="line">68</div><div class="line">69</div><div class="line">70</div><div class="line">71</div><div class="line">72</div><div class="line">73</div><div class="line">74</div><div class="line">75</div><div class="line">76</div><div class="line">77</div><div class="line">78</div><div class="line">79</div><div class="line">80</div><div class="line">81</div><div class="line">82</div><div class="line">83</div><div class="line">84</div><div class="line">85</div><div class="line">86</div><div class="line">87</div><div class="line">88</div><div class="line">89</div><div class="line">90</div><div class="line">91</div><div class="line">92</div><div class="line">93</div><div class="line">94</div><div class="line">95</div><div class="line">96</div><div class="line">97</div><div class="line">98</div><div class="line">99</div><div class="line">100</div><div class="line">101</div><div class="line">102</div><div class="line">103</div><div class="line">104</div></pre></td><td class="code"><pre><div class="line"><span class="keyword">import</span> numpy <span class="keyword">as</span> np</div><div class="line"><span class="keyword">import</span> matplotlib.pyplot <span class="keyword">as</span> plt</div><div class="line"></div><div class="line"></div><div class="line"><span class="function"><span class="keyword">def</span> <span class="title">load_dataset</span><span class="params">(filepath)</span>:</span></div><div class="line">    X = []</div><div class="line">    <span class="keyword">with</span> open(filepath, <span class="string">'r'</span>, encoding=<span class="string">"utf-8"</span>) <span class="keyword">as</span> rf:</div><div class="line">        <span class="keyword">for</span> line <span class="keyword">in</span> rf.readlines():</div><div class="line">            row = line.strip().split(<span class="string">'\t'</span>)</div><div class="line">            fltrow = list(map(float, row))</div><div class="line">            X.append(fltrow)</div><div class="line">    <span class="keyword">return</span> X</div><div class="line"></div><div class="line"></div><div class="line"><span class="function"><span class="keyword">def</span> <span class="title">dist_eclud</span><span class="params">(vec1, vec2)</span>:</span></div><div class="line">    <span class="string">"""calculating the Euclidean distance between twovectors"""</span></div><div class="line">    <span class="keyword">return</span> np.sqrt(np.sum(np.power((vec1 - vec2), <span class="number">2</span>)))</div><div class="line"></div><div class="line"></div><div class="line"><span class="function"><span class="keyword">def</span> <span class="title">rand_cent</span><span class="params">(X, k)</span>:</span></div><div class="line">    n = X.shape[<span class="number">1</span>]</div><div class="line">    centroids = np.mat(np.zeros((k, n)))</div><div class="line">    <span class="keyword">for</span> j <span class="keyword">in</span> range(n):</div><div class="line">        range_min = np.min(X[:, j])</div><div class="line">        range_width = np.max(X[:, j] - range_min)</div><div class="line">        centroids[:, j] = range_min + range_width * np.random.rand(k, <span class="number">1</span>)</div><div class="line">    <span class="keyword">return</span> centroids</div><div class="line"></div><div class="line"></div><div class="line"><span class="function"><span class="keyword">def</span> <span class="title">kmeans</span><span class="params">(X, k, dist_meas=dist_eclud, create_cent=rand_cent)</span>:</span></div><div class="line">    m = X.shape[<span class="number">0</span>]</div><div class="line">    cluster_assment = np.mat(np.zeros((m, <span class="number">2</span>)))</div><div class="line">    centroids = create_cent(X, k)</div><div class="line">    cluster_changed = <span class="keyword">True</span></div><div class="line">    <span class="keyword">while</span> cluster_changed:</div><div class="line">        cluster_changed = <span class="keyword">False</span></div><div class="line">        <span class="keyword">for</span> i <span class="keyword">in</span> range(m):</div><div class="line">            min_dist = np.inf</div><div class="line">            min_idx = <span class="number">-1</span></div><div class="line">            <span class="keyword">for</span> j <span class="keyword">in</span> range(k):</div><div class="line">                dist_ji = dist_meas(centroids[j, :], X[i, :])</div><div class="line">                <span class="keyword">if</span> dist_ji &lt; min_dist:</div><div class="line">                    min_dist = dist_ji</div><div class="line">                    min_idx = j</div><div class="line">            <span class="keyword">if</span> cluster_assment[i, <span class="number">0</span>] != min_idx:</div><div class="line">                cluster_changed = <span class="keyword">True</span></div><div class="line">            cluster_assment[i, :] = min_idx, min_dist ** <span class="number">2</span></div><div class="line">        <span class="comment"># print(centroids)</span></div><div class="line">        <span class="keyword">for</span> cent <span class="keyword">in</span> range(k):</div><div class="line">            pts_in_clust = X[np.nonzero(cluster_assment[:, <span class="number">0</span>].A == cent)[<span class="number">0</span>]]</div><div class="line">            centroids[cent, :] = np.mean(pts_in_clust, axis=<span class="number">0</span>)</div><div class="line">    <span class="keyword">return</span> centroids, cluster_assment</div><div class="line"></div><div class="line"></div><div class="line"><span class="function"><span class="keyword">def</span> <span class="title">bi_kmeans</span><span class="params">(X, k, dist_meas=dist_eclud)</span>:</span></div><div class="line">    m = X.shape[<span class="number">0</span>]</div><div class="line">    cluster_assment = np.mat(np.zeros((m, <span class="number">2</span>)))</div><div class="line">    centroid0 = np.mean(X, axis=<span class="number">0</span>).tolist()[<span class="number">0</span>]</div><div class="line">    cent_list = [centroid0]</div><div class="line">    <span class="keyword">for</span> j <span class="keyword">in</span> range(m):</div><div class="line">        cluster_assment[j, <span class="number">1</span>] = dist_meas(np.mat(centroid0), X[j, :]) ** <span class="number">2</span></div><div class="line">    <span class="keyword">while</span> len(cent_list) &lt; k:</div><div class="line">        lowest_sse = np.inf</div><div class="line">        <span class="keyword">for</span> i <span class="keyword">in</span> range(len(cent_list)):</div><div class="line">            pts_in_curr_cluster = \</div><div class="line">              X[np.nonzero(cluster_assment[:, <span class="number">0</span>].A == i)[<span class="number">0</span>], :]</div><div class="line">            centroid_mat, spl_clust_ass = \</div><div class="line">              kmeans(pts_in_curr_cluster, <span class="number">2</span>, dist_meas)</div><div class="line">            sse_split = np.sum(spl_clust_ass[:, <span class="number">1</span>])</div><div class="line">            sse_not_split = \</div><div class="line">              np.sum(cluster_assment[np.nonzero(cluster_assment[:, <span class="number">0</span>].A != i)[<span class="number">0</span>], <span class="number">1</span>])</div><div class="line">            print(<span class="string">"sse split, and not splist:"</span>, sse_split, sse_not_split)</div><div class="line">            <span class="keyword">if</span> (sse_split + sse_not_split) &lt; lowest_sse:</div><div class="line">                best_cent_to_split = i</div><div class="line">                best_new_cents = centroid_mat</div><div class="line">                best_clust_ass = spl_clust_ass.copy()</div><div class="line">                lowest_sse = sse_split + sse_not_split</div><div class="line">        best_clust_ass[np.nonzero(best_clust_ass[:, <span class="number">0</span>].A == <span class="number">1</span>)[<span class="number">0</span>], <span class="number">0</span>] = len(cent_list)</div><div class="line">        best_clust_ass[np.nonzero(best_clust_ass[:, <span class="number">0</span>].A == <span class="number">0</span>)[<span class="number">0</span>], <span class="number">0</span>] = best_cent_to_split</div><div class="line">        print(<span class="string">'the best center to split is:'</span>, best_cent_to_split)</div><div class="line">        print(<span class="string">'the len of best cluster ass is:'</span>, len(best_clust_ass))</div><div class="line">        cent_list[best_cent_to_split] = best_new_cents[<span class="number">0</span>, :]</div><div class="line">        cent_list.append(best_new_cents[<span class="number">1</span>, :])</div><div class="line">        cluster_assment[np.nonzero(cluster_assment[:, <span class="number">0</span>].A == best_cent_to_split)[<span class="number">0</span>], :] = best_clust_ass</div><div class="line"></div><div class="line">    <span class="keyword">return</span> cent_list, cluster_assment</div><div class="line"></div><div class="line"></div><div class="line"><span class="function"><span class="keyword">def</span> <span class="title">test2</span><span class="params">()</span>:</span></div><div class="line">    filepath = <span class="string">"./Ch10/testSet2.txt"</span></div><div class="line">    X = load_dataset(filepath)</div><div class="line">    x_mat = np.mat(X)</div><div class="line">    cent_list, new_assment = bi_kmeans(x_mat, <span class="number">3</span>)</div><div class="line">    print(cent_list)</div><div class="line">    <span class="comment"># print(new_assment)</span></div><div class="line">    centroids = np.mat(np.zeros((<span class="number">3</span>, <span class="number">2</span>)))</div><div class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> range(len(cent_list)):</div><div class="line">        centroids[i, :] = cent_list[i]</div><div class="line">    plt.scatter(x_mat[:, <span class="number">0</span>].flatten().getA()[<span class="number">0</span>], x_mat[:, <span class="number">1</span>].flatten().getA()[<span class="number">0</span>], color=<span class="string">'blue'</span>)</div><div class="line">    plt.scatter(centroids[:, <span class="number">0</span>].flatten().getA()[<span class="number">0</span>], centroids[:, <span class="number">1</span>].flatten().getA()[<span class="number">0</span>], color=<span class="string">'r'</span>)</div><div class="line">    plt.show()</div><div class="line"></div><div class="line"><span class="keyword">if</span> __name__ == <span class="string">"__main__"</span>:</div><div class="line">    test2()</div></pre></td></tr></table></figure>
<img src="/2017/08/28/K-means-Clustering/markdown-img-paste-20170829103434421.png" alt="bisecting k-means 聚类效果" title="bisecting k-means 聚类效果">

      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      
      
      

      
        <div class="post-nav">
          <div class="post-nav-next post-nav-item">
            
              <a href="/2017/08/28/numpy-note/" rel="next" title="Numpy Note">
                <i class="fa fa-chevron-left"></i> Numpy Note
              </a>
            
          </div>

          <span class="post-nav-divider"></span>

          <div class="post-nav-prev post-nav-item">
            
              <a href="/2017/08/29/Apriori-algorithm/" rel="prev" title="Apriori Algorithm">
                Apriori Algorithm <i class="fa fa-chevron-right"></i>
              </a>
            
          </div>
        </div>
      

      
      
    </footer>
  </div>
  
  
  
  </article>



    <div class="post-spread">
      
    </div>
  </div>


          </div>
          


          
  <div class="comments" id="comments">
    
  </div>


        </div>
        
          
  
  <div class="sidebar-toggle">
    <div class="sidebar-toggle-line-wrap">
      <span class="sidebar-toggle-line sidebar-toggle-line-first"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-middle"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-last"></span>
    </div>
  </div>

  <aside id="sidebar" class="sidebar">
    
    <div class="sidebar-inner">

      

      
        <ul class="sidebar-nav motion-element">
          <li class="sidebar-nav-toc sidebar-nav-active" data-target="post-toc-wrap" >
            文章目录
          </li>
          <li class="sidebar-nav-overview" data-target="site-overview">
            站点概览
          </li>
        </ul>
      

      <section class="site-overview sidebar-panel">
        <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
          <img class="site-author-image" itemprop="image"
               src="/uploads/avatar.jpg"
               alt="东木金" />
          <p class="site-author-name" itemprop="name">东木金</p>
           
              <p class="site-description motion-element" itemprop="description">正在学习机器学习，希望能变得很强！</p>
          
        </div>
        <nav class="site-state motion-element">

          
            <div class="site-state-item site-state-posts">
              <a href="/archives/">
                <span class="site-state-item-count">162</span>
                <span class="site-state-item-name">日志</span>
              </a>
            </div>
          

          
            
            
            <div class="site-state-item site-state-categories">
              <a href="/categories/index.html">
                <span class="site-state-item-count">18</span>
                <span class="site-state-item-name">分类</span>
              </a>
            </div>
          

          
            
            
            <div class="site-state-item site-state-tags">
              <a href="/tags/index.html">
                <span class="site-state-item-count">42</span>
                <span class="site-state-item-name">标签</span>
              </a>
            </div>
          

        </nav>

        

        <div class="links-of-author motion-element">
          
            
              <span class="links-of-author-item">
                <a href="https://github.com/bdmk" target="_blank" title="GitHub">
                  
                    <i class="fa fa-fw fa-github"></i>
                  
                    
                      GitHub
                    
                </a>
              </span>
            
              <span class="links-of-author-item">
                <a href="mailto:catcherchan94@outlook.com" target="_blank" title="E-Mail">
                  
                    <i class="fa fa-fw fa-envelope"></i>
                  
                    
                      E-Mail
                    
                </a>
              </span>
            
          
        </div>

        
        

        
        

        


      </section>

      
      <!--noindex-->
        <section class="post-toc-wrap motion-element sidebar-panel sidebar-panel-active">
          <div class="post-toc">

            
              
            

            
              <div class="post-toc-content"><ol class="nav"><li class="nav-item nav-level-2"><a class="nav-link" href="#普通-K-means"><span class="nav-number">1.</span> <span class="nav-text">普通 K-means</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#算法实现"><span class="nav-number">1.1.</span> <span class="nav-text">算法实现</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#Improving-cluster-performance-with-postprocessing"><span class="nav-number">2.</span> <span class="nav-text">Improving cluster performance with postprocessing</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#算法实现-1"><span class="nav-number">2.1.</span> <span class="nav-text">算法实现</span></a></li></ol></li></ol></div>
            

          </div>
        </section>
      <!--/noindex-->
      

      

    </div>
  </aside>


        
      </div>
    </main>

    <footer id="footer" class="footer">
      <div class="footer-inner">
        <div class="copyright" >
  
  &copy;  2017 - 
  <span itemprop="copyrightYear">2018</span>
  <span class="with-love">
    <i class="fa fa-heart"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">东木金</span>
</div>


<div class="powered-by">
  由 <a class="theme-link" href="https://hexo.io">Hexo</a> 强力驱动
</div>

<div class="theme-info">
  主题 -
  <a class="theme-link" href="https://github.com/iissnan/hexo-theme-next">
    NexT.Gemini
  </a>
</div>


        

        
      </div>
    </footer>

    
      <div class="back-to-top">
        <i class="fa fa-arrow-up"></i>
        
      </div>
    

  </div>

  

<script type="text/javascript">
  if (Object.prototype.toString.call(window.Promise) !== '[object Function]') {
    window.Promise = null;
  }
</script>









  












  
  <script type="text/javascript" src="/lib/jquery/index.js?v=2.1.3"></script>

  
  <script type="text/javascript" src="/lib/fastclick/lib/fastclick.min.js?v=1.0.6"></script>

  
  <script type="text/javascript" src="/lib/jquery_lazyload/jquery.lazyload.js?v=1.9.7"></script>

  
  <script type="text/javascript" src="/lib/velocity/velocity.min.js?v=1.2.1"></script>

  
  <script type="text/javascript" src="/lib/velocity/velocity.ui.min.js?v=1.2.1"></script>

  
  <script type="text/javascript" src="/lib/fancybox/source/jquery.fancybox.pack.js?v=2.1.5"></script>


  


  <script type="text/javascript" src="/js/src/utils.js?v=5.1.2"></script>

  <script type="text/javascript" src="/js/src/motion.js?v=5.1.2"></script>



  
  


  <script type="text/javascript" src="/js/src/affix.js?v=5.1.2"></script>

  <script type="text/javascript" src="/js/src/schemes/pisces.js?v=5.1.2"></script>



  
  <script type="text/javascript" src="/js/src/scrollspy.js?v=5.1.2"></script>
<script type="text/javascript" src="/js/src/post-details.js?v=5.1.2"></script>



  


  <script type="text/javascript" src="/js/src/bootstrap.js?v=5.1.2"></script>



  


  




	





  





  






  

  <script type="text/javascript">
    // Popup Window;
    var isfetched = false;
    var isXml = true;
    // Search DB path;
    var search_path = "search.xml";
    if (search_path.length === 0) {
      search_path = "search.xml";
    } else if (/json$/i.test(search_path)) {
      isXml = false;
    }
    var path = "/" + search_path;
    // monitor main search box;

    var onPopupClose = function (e) {
      $('.popup').hide();
      $('#local-search-input').val('');
      $('.search-result-list').remove();
      $('#no-result').remove();
      $(".local-search-pop-overlay").remove();
      $('body').css('overflow', '');
    }

    function proceedsearch() {
      $("body")
        .append('<div class="search-popup-overlay local-search-pop-overlay"></div>')
        .css('overflow', 'hidden');
      $('.search-popup-overlay').click(onPopupClose);
      $('.popup').toggle();
      var $localSearchInput = $('#local-search-input');
      $localSearchInput.attr("autocapitalize", "none");
      $localSearchInput.attr("autocorrect", "off");
      $localSearchInput.focus();
    }

    // search function;
    var searchFunc = function(path, search_id, content_id) {
      'use strict';

      // start loading animation
      $("body")
        .append('<div class="search-popup-overlay local-search-pop-overlay">' +
          '<div id="search-loading-icon">' +
          '<i class="fa fa-spinner fa-pulse fa-5x fa-fw"></i>' +
          '</div>' +
          '</div>')
        .css('overflow', 'hidden');
      $("#search-loading-icon").css('margin', '20% auto 0 auto').css('text-align', 'center');

      $.ajax({
        url: path,
        dataType: isXml ? "xml" : "json",
        async: true,
        success: function(res) {
          // get the contents from search data
          isfetched = true;
          $('.popup').detach().appendTo('.header-inner');
          var datas = isXml ? $("entry", res).map(function() {
            return {
              title: $("title", this).text(),
              content: $("content",this).text(),
              url: $("url" , this).text()
            };
          }).get() : res;
          var input = document.getElementById(search_id);
          var resultContent = document.getElementById(content_id);
          var inputEventFunction = function() {
            var searchText = input.value.trim().toLowerCase();
            var keywords = searchText.split(/[\s\-]+/);
            if (keywords.length > 1) {
              keywords.push(searchText);
            }
            var resultItems = [];
            if (searchText.length > 0) {
              // perform local searching
              datas.forEach(function(data) {
                var isMatch = false;
                var hitCount = 0;
                var searchTextCount = 0;
                var title = data.title.trim();
                var titleInLowerCase = title.toLowerCase();
                var content = data.content.trim().replace(/<[^>]+>/g,"");
                var contentInLowerCase = content.toLowerCase();
                var articleUrl = decodeURIComponent(data.url);
                var indexOfTitle = [];
                var indexOfContent = [];
                // only match articles with not empty titles
                if(title != '') {
                  keywords.forEach(function(keyword) {
                    function getIndexByWord(word, text, caseSensitive) {
                      var wordLen = word.length;
                      if (wordLen === 0) {
                        return [];
                      }
                      var startPosition = 0, position = [], index = [];
                      if (!caseSensitive) {
                        text = text.toLowerCase();
                        word = word.toLowerCase();
                      }
                      while ((position = text.indexOf(word, startPosition)) > -1) {
                        index.push({position: position, word: word});
                        startPosition = position + wordLen;
                      }
                      return index;
                    }

                    indexOfTitle = indexOfTitle.concat(getIndexByWord(keyword, titleInLowerCase, false));
                    indexOfContent = indexOfContent.concat(getIndexByWord(keyword, contentInLowerCase, false));
                  });
                  if (indexOfTitle.length > 0 || indexOfContent.length > 0) {
                    isMatch = true;
                    hitCount = indexOfTitle.length + indexOfContent.length;
                  }
                }

                // show search results

                if (isMatch) {
                  // sort index by position of keyword

                  [indexOfTitle, indexOfContent].forEach(function (index) {
                    index.sort(function (itemLeft, itemRight) {
                      if (itemRight.position !== itemLeft.position) {
                        return itemRight.position - itemLeft.position;
                      } else {
                        return itemLeft.word.length - itemRight.word.length;
                      }
                    });
                  });

                  // merge hits into slices

                  function mergeIntoSlice(text, start, end, index) {
                    var item = index[index.length - 1];
                    var position = item.position;
                    var word = item.word;
                    var hits = [];
                    var searchTextCountInSlice = 0;
                    while (position + word.length <= end && index.length != 0) {
                      if (word === searchText) {
                        searchTextCountInSlice++;
                      }
                      hits.push({position: position, length: word.length});
                      var wordEnd = position + word.length;

                      // move to next position of hit

                      index.pop();
                      while (index.length != 0) {
                        item = index[index.length - 1];
                        position = item.position;
                        word = item.word;
                        if (wordEnd > position) {
                          index.pop();
                        } else {
                          break;
                        }
                      }
                    }
                    searchTextCount += searchTextCountInSlice;
                    return {
                      hits: hits,
                      start: start,
                      end: end,
                      searchTextCount: searchTextCountInSlice
                    };
                  }

                  var slicesOfTitle = [];
                  if (indexOfTitle.length != 0) {
                    slicesOfTitle.push(mergeIntoSlice(title, 0, title.length, indexOfTitle));
                  }

                  var slicesOfContent = [];
                  while (indexOfContent.length != 0) {
                    var item = indexOfContent[indexOfContent.length - 1];
                    var position = item.position;
                    var word = item.word;
                    // cut out 100 characters
                    var start = position - 20;
                    var end = position + 80;
                    if(start < 0){
                      start = 0;
                    }
                    if (end < position + word.length) {
                      end = position + word.length;
                    }
                    if(end > content.length){
                      end = content.length;
                    }
                    slicesOfContent.push(mergeIntoSlice(content, start, end, indexOfContent));
                  }

                  // sort slices in content by search text's count and hits' count

                  slicesOfContent.sort(function (sliceLeft, sliceRight) {
                    if (sliceLeft.searchTextCount !== sliceRight.searchTextCount) {
                      return sliceRight.searchTextCount - sliceLeft.searchTextCount;
                    } else if (sliceLeft.hits.length !== sliceRight.hits.length) {
                      return sliceRight.hits.length - sliceLeft.hits.length;
                    } else {
                      return sliceLeft.start - sliceRight.start;
                    }
                  });

                  // select top N slices in content

                  var upperBound = parseInt('1');
                  if (upperBound >= 0) {
                    slicesOfContent = slicesOfContent.slice(0, upperBound);
                  }

                  // highlight title and content

                  function highlightKeyword(text, slice) {
                    var result = '';
                    var prevEnd = slice.start;
                    slice.hits.forEach(function (hit) {
                      result += text.substring(prevEnd, hit.position);
                      var end = hit.position + hit.length;
                      result += '<b class="search-keyword">' + text.substring(hit.position, end) + '</b>';
                      prevEnd = end;
                    });
                    result += text.substring(prevEnd, slice.end);
                    return result;
                  }

                  var resultItem = '';

                  if (slicesOfTitle.length != 0) {
                    resultItem += "<li><a href='" + articleUrl + "' class='search-result-title'>" + highlightKeyword(title, slicesOfTitle[0]) + "</a>";
                  } else {
                    resultItem += "<li><a href='" + articleUrl + "' class='search-result-title'>" + title + "</a>";
                  }

                  slicesOfContent.forEach(function (slice) {
                    resultItem += "<a href='" + articleUrl + "'>" +
                      "<p class=\"search-result\">" + highlightKeyword(content, slice) +
                      "...</p>" + "</a>";
                  });

                  resultItem += "</li>";
                  resultItems.push({
                    item: resultItem,
                    searchTextCount: searchTextCount,
                    hitCount: hitCount,
                    id: resultItems.length
                  });
                }
              })
            };
            if (keywords.length === 1 && keywords[0] === "") {
              resultContent.innerHTML = '<div id="no-result"><i class="fa fa-search fa-5x" /></div>'
            } else if (resultItems.length === 0) {
              resultContent.innerHTML = '<div id="no-result"><i class="fa fa-frown-o fa-5x" /></div>'
            } else {
              resultItems.sort(function (resultLeft, resultRight) {
                if (resultLeft.searchTextCount !== resultRight.searchTextCount) {
                  return resultRight.searchTextCount - resultLeft.searchTextCount;
                } else if (resultLeft.hitCount !== resultRight.hitCount) {
                  return resultRight.hitCount - resultLeft.hitCount;
                } else {
                  return resultRight.id - resultLeft.id;
                }
              });
              var searchResultList = '<ul class=\"search-result-list\">';
              resultItems.forEach(function (result) {
                searchResultList += result.item;
              })
              searchResultList += "</ul>";
              resultContent.innerHTML = searchResultList;
            }
          }

          if ('auto' === 'manual') {
            input.addEventListener('input', inputEventFunction);
          } else {
            $('.search-icon').click(inputEventFunction);
            input.addEventListener('keypress', function (event) {
              if (event.keyCode === 13) {
                inputEventFunction();
              }
            });
          }

          // remove loading animation
          $(".local-search-pop-overlay").remove();
          $('body').css('overflow', '');

          proceedsearch();
        }
      });
    }

    // handle and trigger popup window;
    $('.popup-trigger').click(function(e) {
      e.stopPropagation();
      if (isfetched === false) {
        searchFunc(path, 'local-search-input', 'local-search-result');
      } else {
        proceedsearch();
      };
    });

    $('.popup-btn-close').click(onPopupClose);
    $('.popup').click(function(e){
      e.stopPropagation();
    });
    $(document).on('keyup', function (event) {
      var shouldDismissSearchPopup = event.which === 27 &&
        $('.search-popup').is(':visible');
      if (shouldDismissSearchPopup) {
        onPopupClose();
      }
    });
  </script>





  

  

  

  
  
    <script type="text/x-mathjax-config">
      MathJax.Hub.Config({
        tex2jax: {
          inlineMath: [ ['$','$'], ["\\(","\\)"]  ],
          processEscapes: true,
          skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code']
        }
      });
    </script>

    <script type="text/x-mathjax-config">
      MathJax.Hub.Queue(function() {
        var all = MathJax.Hub.getAllJax(), i;
        for (i=0; i < all.length; i += 1) {
          all[i].SourceElement().parentNode.className += ' has-jax';
        }
      });
    </script>
    <script type="text/javascript" src="//cdn.bootcss.com/mathjax/2.7.1/latest.js?config=TeX-AMS-MML_HTMLorMML"></script>
  


  

  

</body>
</html>
